In everyday life, networks of choices set forth in a particular order or hierarchy are encountered with increasing frequency. Usually, it is desired to traverse the network in the most efficient manner possible to accomplish a particular goal.
In modem mathematics, graph theory is used to study networks of hierarchical choices. The hierarchical networks can be represented as a graph structure. Graph theory finds practical applications in chemistry, computer science, economics, electronics and linguistics.
A graph structure is a collection of points, called “vertices”, and a collection of lines, called “edges”. Each edge joins a pair of vertices or a single point to itself.
A simple example of a network represented by a graph structure is a road map. The vertices represent towns or cities. The edges represent the roads that connect the towns and cities.
Another type of network familiar to anyone who has a telephone is an automated telephone voice response system, such as commonly utilized by many large companies, to direct incoming calls to particular individuals or departments or to assist the caller in performing a transaction, such as making a purchase.
That type of telephone network can also be represented as a graph structure. When the system answers an incoming call, it transmits a verbal description or prompt to the caller: “If you would like to speak to Harry, press 1; if you would like to speak to Fred, press 2”. (In general, we will use “verbal description” to mean a set of words relating to the subject matter whether presented audibly or in written form. The verbal descriptions may range from a few words to an entire document worth of text). A first vertex on the graph represents the initial prompt, which a caller hears upon reaching the telephone response system. If the user's response is pressing 1, calls are directed along a first edge to Harry, represented by a second vertex. If the response is pressing 2, the call is directed along a second edge to Fred, represented by a third vertex. Then, if the chosen person is not available, the caller is asked whether the caller wishes to leave a message. If the response is positive, the caller is directed along another edge to the selected person's voice mail, which would be represented by another vertex of the graph.
In general, whether for a telephone response network or for any other application representable by a graph structure, the caller or user of the system will have some goal. By “goal” we mean a combination of transactions and information accesses which the user seeks to accomplish. By “transaction” we mean an operation performed electronically with a user. In general, there will also be a combination of vertices or nodes in the graph that best represent or are closest to the goal the user is trying to accomplish. We call these vertices the “goal vertices”.
For the user, the object in navigating the graph is to get from the first vertex to the goal vertices. If this is not done as quickly and efficiently as possible the user may become frustrated and give up. Moreover, as the number of possible choices or nodes in the network becomes larger, the number of possible pathways between the first vertex and the goal vertices multiplies rapidly. Therefore, the ability to reach the goal vertex can become more difficult, require navigation of an excessive number of choices or nodes, or discourage a user before the goal vertex is even reached.